{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #装饰树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: expandBinaryTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #装饰树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "力扣嘉年华上的 DIY 手工展位准备了一棵缩小版的 **二叉** 装饰树 `root` 和灯饰，你需要将灯饰逐一插入装饰树中，要求如下：\n",
    "\n",
    "- 完成装饰的二叉树根结点与 `root` 的根结点值相同\n",
    "- 若一个节点拥有父节点，则在该节点和他的父节点之间插入一个灯饰（即插入一个值为 `-1` 的节点）。具体地：\n",
    "    - 在一个 父节点 x 与其左子节点 y 之间添加 -1 节点， 节点 -1、节点 y 为各自父节点的左子节点，\n",
    "    - 在一个 父节点 x 与其右子节点 y 之间添加 -1 节点， 节点 -1、节点 y 为各自父节点的右子节点，\n",
    "    \n",
    "现给定二叉树的根节点 `root` ，请返回完成装饰后的树的根节点。\n",
    "**示例 1：**\n",
    ">输入：\n",
    ">`root = [7,5,6]`\n",
    ">\n",
    ">输出：`[7,-1,-1,5,null,null,6]`\n",
    ">\n",
    ">解释：如下图所示，\n",
    ">![image.png](https://pic.leetcode-cn.com/1663575757-yRLGaq-image.png){:width=400px}\n",
    "\n",
    "**示例 2：**\n",
    ">输入：\n",
    ">`root = [3,1,7,3,8,null,4]`\n",
    ">\n",
    ">输出：`[3,-1,-1,1,null,null,7,-1,-1,null,-1,3,null,null,8,null,4]`\n",
    ">\n",
    ">解释：如下图所示\n",
    "![image.png](https://pic.leetcode-cn.com/1663577920-sjrAYH-image.png){:width=500px}\n",
    "\n",
    "**提示：**\n",
    ">`0 <= root.Val <= 1000`\n",
    ">`root` 节点数量范围为 `[1, 10^5]`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [KnLfVT](https://leetcode.cn/problems/KnLfVT/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [KnLfVT](https://leetcode.cn/problems/KnLfVT/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,5,6]', '[3,1,7,3,8,null,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left: root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right: root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(nd):\n",
    "            if nd.left:\n",
    "                dfs(nd.left)\n",
    "                n1 = TreeNode(-1)\n",
    "                n1.left=nd.left\n",
    "                nd.left = n1\n",
    "            if nd.right:\n",
    "                dfs(nd.right)\n",
    "                n1 = TreeNode(-1)\n",
    "                n1.right=nd.right\n",
    "                nd.right=n1\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left:\n",
    "            dec = TreeNode(-1)\n",
    "            left = root.left\n",
    "            root.left = dec\n",
    "            dec.left = left\n",
    "            self.expandBinaryTree(left)\n",
    "        if root.right:\n",
    "            dec = TreeNode(-1)\n",
    "            right = root.right\n",
    "            root.right = dec\n",
    "            dec.right = right\n",
    "            self.expandBinaryTree(right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def f(x):\n",
    "            if x.right:\n",
    "                newnode = TreeNode(-1)\n",
    "                newnode.right = x.right\n",
    "                x.right = newnode\n",
    "                f(newnode.right)\n",
    "            if x.left:\n",
    "                newnode = TreeNode(-1)\n",
    "                newnode.left = x.left\n",
    "                x.left = newnode\n",
    "                f(newnode.left)\n",
    "        node = root\n",
    "        f(node)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left:\n",
    "            root.left=TreeNode(-1,left=self.expandBinaryTree(root.left))\n",
    "        if root.right:\n",
    "            root.right=TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left is not None:\n",
    "            left = self.expandBinaryTree(root.left)\n",
    "            dec = TreeNode(-1)\n",
    "            dec.left = left\n",
    "            root.left = dec\n",
    "        if root.right is not None:\n",
    "            right = self.expandBinaryTree(root.right)\n",
    "            dec = TreeNode(-1)\n",
    "            dec.right = right\n",
    "            root.right = dec\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.walk(root)\n",
    "        return root\n",
    "\n",
    "    def walk(self,node):\n",
    "        if node is None:\n",
    "            return\n",
    "        \n",
    "        if node.left is not None:\n",
    "            t=node.left\n",
    "            node.left=TreeNode(-1,t)\n",
    "            self.walk(t)\n",
    "        if node.right is not None:\n",
    "            t=node.right\n",
    "            self.walk(t)\n",
    "            node.right=TreeNode(-1,right=t)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        if root.left is None and root.right is None:\n",
    "            return root\n",
    "        \n",
    "        if root.left is not None:\n",
    "            tmp = root.left\n",
    "            root.left = TreeNode(-1)\n",
    "            root.left.left = self.expandBinaryTree(tmp)\n",
    "        if root.right is not None:\n",
    "            tmp = root.right\n",
    "            root.right = TreeNode(-1)\n",
    "            root.right.right = self.expandBinaryTree(tmp)\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node, parent):\n",
    "            if node is None:\n",
    "                return\n",
    "            if parent is not None:\n",
    "                if parent.left == node:\n",
    "                    parent.left = TreeNode(-1, node)\n",
    "                else:\n",
    "                    parent.right = TreeNode(-1, right=node)\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "\n",
    "        dfs(root, None)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left:\n",
    "            node = root.left\n",
    "            root.left = TreeNode(-1)\n",
    "            root.left.left = node\n",
    "            self.expandBinaryTree(node)\n",
    "        if root.right:\n",
    "            node = root.right\n",
    "            root.right = TreeNode(-1)\n",
    "            root.right.right = node\n",
    "            self.expandBinaryTree(node)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return root\n",
    "        def bfs(node):\n",
    "            pre_left = node.left\n",
    "            pre_right = node.right\n",
    "            if node.left:\n",
    "                node.left = TreeNode(-1, left=pre_left)\n",
    "                bfs(pre_left)\n",
    "            if node.right:\n",
    "                node.right = TreeNode(-1, right=pre_right )\n",
    "                bfs(pre_right)\n",
    "        bfs(root)\n",
    "        return root\n",
    "\n",
    "        \n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def bfs(node):\n",
    "            pre_left = node.left\n",
    "            pre_right = node.right\n",
    "            if node.left:\n",
    "                node.left = TreeNode(-1, left=pre_left)\n",
    "                bfs(pre_left)\n",
    "            if node.right:\n",
    "                node.right = TreeNode(-1, right=pre_right )\n",
    "                bfs(pre_right)\n",
    "        bfs(root)\n",
    "        return root\n",
    "\n",
    "        \n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left:\n",
    "            root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right:\n",
    "            root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left: \n",
    "            root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right: \n",
    "            root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            if cur.left:\n",
    "                ln = cur.left\n",
    "                new_cur = TreeNode(-1)\n",
    "                cur.left = new_cur\n",
    "                new_cur.left = ln\n",
    "                queue.append(ln)                    \n",
    "\n",
    "            if cur.right:\n",
    "                rn = cur.right\n",
    "                new_cur = TreeNode(-1)\n",
    "                cur.right = new_cur\n",
    "                new_cur.right = rn\n",
    "                queue.append(rn)   \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # 前序遍历后在中间插入\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "            if root.left:\n",
    "                l = root.left\n",
    "                root.left = TreeNode(-1)\n",
    "                root.left.left = l\n",
    "                dfs(root.left.left)\n",
    "            if root.right:\n",
    "                r = root.right\n",
    "                root.right = TreeNode(-1)\n",
    "                root.right.right = r\n",
    "                dfs(root.right.right)\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left: \n",
    "            root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right: \n",
    "            root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left != None:\n",
    "            root.left = TreeNode(-1, self.expandBinaryTree(root.left), None)\n",
    "        if root.right != None:\n",
    "            root.right = TreeNode(-1, None, self.expandBinaryTree(root.right))\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left:\n",
    "            root.left =  TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right:\n",
    "            root.right = TreeNode(-1, right = self.expandBinaryTree(root.right))\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left: \n",
    "            root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right: \n",
    "            root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left: root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right: root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        if root.left:\n",
    "            left = self.expandBinaryTree(root.left)\n",
    "            lnd = TreeNode(-1)\n",
    "            lnd.left = left\n",
    "            root.left = lnd\n",
    "        if root.right:\n",
    "            right = self.expandBinaryTree(root.right)\n",
    "            rnd = TreeNode(-1)\n",
    "            rnd.right = right\n",
    "            root.right = rnd\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left:\n",
    "            root.left = TreeNode(-1,left = self.expandBinaryTree(root.left))\n",
    "        if root.right:\n",
    "            root.right = TreeNode(-1,right = self.expandBinaryTree(root.right))\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        #copy\n",
    "        if root.left:\n",
    "            root.left = TreeNode(-1,left = self.expandBinaryTree(root.left))\n",
    "        if root.right:\n",
    "            root.right = TreeNode(-1,right = self.expandBinaryTree(root.right))\n",
    "        return  root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left: root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right: root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left: root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right: root.right = TreeNode(-1, right = self.expandBinaryTree(root.right))\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left: root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right: root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        while len(queue) > 0:   # 队列存每一层节点\n",
    "            n = len(queue)\n",
    "            for i in range(n):\n",
    "                node = queue.popleft()\n",
    "                if node.left:\n",
    "                    cur = node.left\n",
    "                    insert = TreeNode(val=-1,left=cur)\n",
    "                    node.left = insert\n",
    "                    queue.append(cur)\n",
    "                if node.right:\n",
    "                    cur = node.right\n",
    "                    insert = TreeNode(val=-1,right=cur)\n",
    "                    node.right = insert\n",
    "                    queue.append(cur)\n",
    "        return root\n",
    "\n",
    "\n",
    "        \n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        #copy\n",
    "        if root.left:\n",
    "            root.left = TreeNode(-1,left = self.expandBinaryTree(root.left))\n",
    "        if root.right:\n",
    "            root.right = TreeNode(-1,right = self.expandBinaryTree(root.right))\n",
    "        return  root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root:\n",
    "            if root.left:\n",
    "                root.left = TreeNode(val=-1, left=self.expandBinaryTree(root.left), right=None)\n",
    "            if root.right:\n",
    "                root.right = TreeNode(val=-1, right=self.expandBinaryTree(root.right), left=None)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left: \n",
    "            root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right: \n",
    "            root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left: root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right: root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # 前序遍历后在中间插入\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "            if root.left:\n",
    "                l = root.left\n",
    "                root.left = TreeNode(-1)  # 插入结点\n",
    "                root.left.left = l\n",
    "                dfs(root.left.left)  # 注意这里由于多了一个结点，需要dfs(root.left.left)\n",
    "            if root.right:\n",
    "                r = root.right\n",
    "                root.right = TreeNode(-1)\n",
    "                root.right.right = r\n",
    "                dfs(root.right.right)\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left: \n",
    "            root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right: \n",
    "            root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def insertNode(root):\n",
    "            if root.left:\n",
    "                root.left=TreeNode(-1,left=root.left)\n",
    "                insertNode(root.left.left)\n",
    "            if root.right:\n",
    "                root.right=TreeNode(-1,right=root.right)\n",
    "                insertNode(root.right.right)\n",
    "        if root:\n",
    "            insertNode(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.walk(root)\n",
    "        return root\n",
    "\n",
    "    def walk(self,node):\n",
    "        if node is None:\n",
    "            return\n",
    "        \n",
    "        if node.left is not None:\n",
    "            t=node.left\n",
    "            node.left=TreeNode(-1,t)\n",
    "            self.walk(t)\n",
    "        if node.right is not None:\n",
    "            t=node.right\n",
    "            self.walk(t)\n",
    "            node.right=TreeNode(-1,right=t)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root==None:\n",
    "            return None\n",
    "        def DPS(node):\n",
    "            if node.left !=None:\n",
    "                b=TreeNode(-1,node.left,None)\n",
    "                node.left=b\n",
    "                DPS(b.left)\n",
    "            if node.right !=None:\n",
    "                b=TreeNode(-1,None,node.right)\n",
    "                node.right=b\n",
    "                DPS(b.right)\n",
    "        DPS(root)\n",
    "        return root\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        while len(queue) > 0:   # 队列存每一层节点\n",
    "            n = len(queue)\n",
    "            for i in range(n):\n",
    "                node = queue.popleft()\n",
    "                if node.left:\n",
    "                    cur = node.left\n",
    "                    insert = TreeNode(val=-1,left=cur)\n",
    "                    node.left = insert\n",
    "                    queue.append(cur)\n",
    "                if node.right:\n",
    "                    cur = node.right\n",
    "                    insert = TreeNode(val=-1,right=cur)\n",
    "                    node.right = insert\n",
    "                    queue.append(cur)\n",
    "        return root\n",
    "\n",
    "\n",
    "        \n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(root):\n",
    "            if root == None:\n",
    "                return\n",
    "            if root.left:\n",
    "                left = root.left\n",
    "                root.left = TreeNode(-1)\n",
    "                root.left.left = left\n",
    "                dfs(left)\n",
    "            if root.right:\n",
    "                right = root.right\n",
    "                root.right = TreeNode(-1)\n",
    "                root.right.right = right\n",
    "                dfs(right)\n",
    "            return root\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left: root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right: root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left: \n",
    "            root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right: \n",
    "            root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(nd):\n",
    "            if nd.left:\n",
    "                n1 = TreeNode(-1)\n",
    "                n1.left = nd.left\n",
    "                nd.left = n1\n",
    "                dfs(n1.left)\n",
    "            if nd.right:\n",
    "                n1 = TreeNode(-1)\n",
    "                n1.right = nd.right\n",
    "                nd.right = n1\n",
    "                dfs(n1.right)\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def decorate(root) -> Optional[TreeNode]:\n",
    "            if root.left is None and root.right is None:\n",
    "                return root\n",
    "            if root.left:\n",
    "                temp = TreeNode(-1)\n",
    "                temp.left = root.left\n",
    "                root.left = temp\n",
    "                temp.left = decorate(temp.left)\n",
    "            if root.right:\n",
    "                temp = TreeNode(-1)\n",
    "                temp.right = root.right\n",
    "                root.right = temp\n",
    "                temp.right = decorate(temp.right)\n",
    "            return root\n",
    "        return decorate(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left:\n",
    "            root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right:\n",
    "            root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left:\n",
    "            root.left = TreeNode(-1,left = self.expandBinaryTree(root.left))\n",
    "        if root.right:\n",
    "            root.right = TreeNode(-1,right = self.expandBinaryTree(root.right))\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left:\n",
    "            root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right:\n",
    "            root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left: root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right: root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:return root\n",
    "        if root.left: root.left = TreeNode(-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right: root.right = TreeNode(-1, right=self.expandBinaryTree(root.right))\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # def trim_tree(node):\n",
    "        #     if not node:\n",
    "        #         return\n",
    "        #     if node.left:\n",
    "        #         node.left = TreeNode(val=-1, left=node.left)\n",
    "        #         trim_tree(node.left.left)\n",
    "        #     if node.right:\n",
    "        #         node.right = TreeNode(val=-1, right=node.right)\n",
    "        #         trim_tree(node.right.right)\n",
    "        #     return node\n",
    "\n",
    "        # return trim_tree(root)\n",
    "\n",
    "        # ------------------------\n",
    "        if root.left:\n",
    "            root.left = TreeNode(val=-1, left=self.expandBinaryTree(root.left))\n",
    "        if root.right:\n",
    "            root.right = TreeNode(val=-1, right=self.expandBinaryTree(root.right))\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(node:TreeNode):\n",
    "            if not node:\n",
    "                return\n",
    "            if node.left:\n",
    "                left = node.left\n",
    "                new_node = TreeNode(-1)\n",
    "                node.left = new_node\n",
    "                new_node.left = left\n",
    "                dfs(new_node.left)\n",
    "            if node.right:\n",
    "                right = node.right\n",
    "                new_node = TreeNode(-1)\n",
    "                node.right = new_node\n",
    "                new_node.right = right\n",
    "                dfs(new_node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "    # Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(nd):\n",
    "            if nd.left:\n",
    "                dfs(nd.left)\n",
    "                n1 = TreeNode(-1)\n",
    "                n1.left=nd.left\n",
    "                nd.left = n1\n",
    "            if nd.right:\n",
    "                dfs(nd.right)\n",
    "                n1 = TreeNode(-1)\n",
    "                n1.right=nd.right\n",
    "                nd.right=n1\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        def dfs(nd):\n",
    "            if nd.left:\n",
    "                dfs(nd.left)\n",
    "                n1 = TreeNode(-1)\n",
    "                n1.left=nd.left\n",
    "                nd.left = n1\n",
    "            if nd.right:\n",
    "                dfs(nd.right)\n",
    "                n1 = TreeNode(-1)\n",
    "                n1.right=nd.right\n",
    "                nd.right=n1\n",
    "        dfs(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)  \n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            if cur.left is not None:\n",
    "                queue.append(cur.left)\n",
    "                cur.left = TreeNode(val=-1,left=cur.left)\n",
    "            if cur.right is not None:\n",
    "                queue.append(cur.right)\n",
    "                cur.right = TreeNode(val=-1,right=cur.right)   \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        que = deque()\n",
    "        que.append(root)        \n",
    "        while que:\n",
    "            node = que.popleft()            \n",
    "            if node.left:\n",
    "                if node.val != -1:\n",
    "                    tmp = TreeNode(val=-1)\n",
    "                    tmp.left = node.left\n",
    "                    node.left = tmp\n",
    "                    \n",
    "                que.append(node.left)\n",
    "                \n",
    "            if node.right:\n",
    "                if node.val != -1:\n",
    "                    tmp = TreeNode(val=-1)\n",
    "                    tmp.right = node.right\n",
    "                    node.right = tmp\n",
    "                    \n",
    "                que.append(node.right)\n",
    "                \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # 前序遍历后在中间插入\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "            if root.left:\n",
    "                l = root.left\n",
    "                root.left = TreeNode(-1)  # 插入结点\n",
    "                root.left.left = l\n",
    "                dfs(root.left.left)  # 注意这里由于多了一个结点，需要dfs(root.left.left)\n",
    "            if root.right:\n",
    "                r = root.right\n",
    "                root.right = TreeNode(-1)\n",
    "                root.right.right = r\n",
    "                dfs(root.right.right)\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def expandBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root.left:\n",
    "            root.left = TreeNode(-1,left=self.expandBinaryTree(root.left))\n",
    "        if root.right:\n",
    "            root.right = TreeNode(-1,right=self.expandBinaryTree(root.right))\n",
    "        return root\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
